Cache

组成方式

Cache 组成部件：

• Cache line：Cache 不是一个字节一个字节地存，而是一块一块地存，这一块被称为 Cache line。
  因为访问了一个地址，附近地址很可能马上也会访问，采取这种方式可以减少开销。
• Cache set：同一行 Cache line 合称为 Cache set，一个 n 路组相联 Cache 就是指 set 中包含 n 个 line。
• Offset：是指在 Cache line 中的偏移

一个内存块映射到 Cache 的数据位置，有三种映射方式：

• 直接映射：固定的内存块对应固定的 Cache line，比如内存块 0，2，4，8 对应 line 0。
  这样实现简单，计算快速，但是冲突严重，如果反复读取内存块 0 和 4，就要不断切换。
• 全映射：任意内存块对应任意 Cache line，比如内存块 0 可以放在 line 3 也可以放在 7。
  这样冲突最少，但是每次找位置需要从把所有 Cache 查一遍，如果 Cahce 很大就要查找半天。
• 组映射：固定的内存块对应固定的 Cache set，比如内存块 0 可以放在 set 0 中的任何一个 line 中。
  这样折中了上面两个方式。

一个内存地址通常被拆成 Tag、Index、Offset 三段，含义为：

• Tag：判断该位置 Cache line 中是否存放目标地址数据。
• Index：判断去哪一个 Cache set。
• Offset：判断从 Cache line 取哪一个字节

由于以上结构，在实践中会有这些多级 Cache 结构：

• L1 一般用 SRAM 实现，分为 I-cache 和 D-cache，最快。
• L2 指令和数据共享，采用哈佛结构，更慢。主要目的是保存尽可能多指令。
• L3 更大，一般L3是每个核共享的，有时L2也是。

访存策略

Cache 和 Memory 之间有多种策略：

• 写回：为了减少 Cache 和内存的访问延迟，可以做标记，直到成脏数据再写回。
• 写通：直接写，不管延迟。

如果写入地址不在 Dcache，就发生了写缺失，如果直接写到下级存储器，就叫做 Non-Write Allocate 对应的就是Write Allocate，先取出相应数据块和修改值合并在Dcache 这里不能直接找一个地址写，或者会造成cache和memory的不一致性

替换策略姑且不看，太过深了

优化方式

Cache有3C原则：Compulsory，Capcity，Conflict，也就是强制性未命中，容量未命中，冲突未命中。

分别含义为：第一次访问失效，由于容量满引发的 miss，有多个数据映射到 Cache 同一个位置

对应的解决方法就是加大大小，预取，Victim Cache。

访问方式

有两种访问方式：

• 并行：Tag 和 Data 同时找，每个都是直接比对，最后拿各自结果在多路选择器选择。由于电路增多，延迟和功耗会增加，但是流水级少一级
• 串行：一个一个比对 Tag 再去找 Data。更好提频率，功耗低。

写缓存

在Cache写回下级存储器的时候，可以加个写缓存，等有空写入，这时候这个line就空出来了。 L1 通常用这个

流水线

由于读可以并行和串行，写只能串行，以写为例 一个经典的设计方式是：Tag 读取和比较->写 data store 和 load 要注意是有可能在 cache 流水线有数据前递的可能。

多级结构

就是L1, L2，L3 对于我们这个小结构，目前来说感觉两级够了 然后有两种策略：inclusive和Exclusive，就是下级存储器是否包含上级存储器数据，两者优缺点显而易见 差距不大个人认为实现inclusive更好

Victim Cache

在L1丢弃的数据，实际上也有很大的概率是需要的，可以在L1和L2中间插入一个Victim Cache，通常采用全相连，来暂时保留数据 有种类似设计叫做 Filter Cache，这个是放在进入Cache前的，这样可以过滤掉偶尔使用的数据（感觉有点脱裤子放屁

预取

就是预测技术，为了避免预测失败污染cache，一般会加个Stream Buffer，作为单独缓存，这是icache常用做法 在cache上使用预取要注意是否值当

多端口

d

多端口是必须的，但是多端口会造成延迟增加，所以现实世界没有采取真正的多端口设计的cpu 现在用的是bank，也就是把cache分成多个bank，每个bank有个端口，只有访问同一个bank才会出现冲突 这样data sram就不需要复制接口，只有tag有。 也就是说一个64KB的Cache，采用2路，需要VA[14:0]寻址，每个数据块64字节，所以set要用[14:6]，字节要有[5:0]，每个line分成8个bank，那么[5:3]是bank的序号 每个way必然要存储自己的tag，所以要复制一份

i

有种方式提供多指令，那就是直接一口气打包过去，但是如果包不全，容易让指令空转。 所以部分处理器每周期会取出比能解码更多的指令，取值和解码中间加个buffer。

当然有更暴力的解法，那就是直接扩大cache line的空间，比如8个就能让4个指令更有可能在同一个cache line中，在cache不变的情况下，会减少cache set个数，导致更容易miss 但是你不能随意增加sram数量，sram增设本身会增加保护电路的面积，所以更好的是4个sram，每个line多包含一个。在设计重排顺序电路合并一起

虚拟存储器

概念

虚拟地址的必要

如果程序直接使用物理地址，会有几个大问题：

• 程序很难写：每次运行时物理内存位置可能不同
• 程序不安全：一个程序可能随便读写另一个程序的内存
• 内存不好管理：程序需要连续大内存时，物理内存未必连续

虚拟地址解决的是：每个程序都以为自己有一整片连续内存，由操作系统和 MMU 在背后把它映射到真实物理内存。

分页管理内存

分页的意思是：把虚拟内存切成固定大小的小块，把物理内存也切成同样大小的小块。通常一页是 4kb 大小。

虚拟地址可以拆成虚拟页号 + 页内偏移，对应物理页号 + 页内偏移

多级页表

页的信息肯定需要一个页表管理，以下信息会存放在页表中：

• 虚拟页映射到哪个物理页？
• 这个页能不能读？
• 能不能写？
• 能不能执行？
• 在不在内存里？
• 有没有被访问过？
• 有没有被写脏？

我们可以想象如果把整个虚拟地址空间做成一张大表，我们设虚拟地址空间 = 4GB，页大小 = 4KB。

那么页数量 = 4GB / 4KB = 1,048,576 页

如果每个 PTE 4 字节，那么一个进程的页表就要：1,048,576 * 4 = 4MB

这非常浪费，许多程序用不了这么多，所以要采取多级页表

多级页表就是说，先用一级页表找到二级页表；再用二级页表找到真正的 PTE。如果某一大片虚拟地址根本没用，就不需要给它分配下面的页表。

MMU

MMU 用来翻译虚拟页号和物理页号，判断页的权限，判断页的状态。

CPU -> 虚拟地址 -> MMU -> 物理地址 -> Cache/内存

如果虚拟地址不正常它会产生异常

它还需要管理页的访问位（这个页最近有没有被读/写过）和脏位（这个页有没有被写过），这些值需要 MMU 自动设置，由操作系统查看和清理

TLB

如果每次访存都查页表，会很慢，因为页表本身也在内存里。所以 CPU 里有一个缓存，专门缓存地址翻译结果，叫做 TLB。

TLB 缓存物理页号和权限

分支预测

没有很深地接触，暂时不写。

前端

没有很深地接触，暂时不写。

后端

后端这块设计是乱序 CPU 的核心所在，也可以说是人类工艺制品中最复杂的产物之一。

其实思路就是并发，当先辈们对 CPU 设计逐渐炉火纯青的时候，自然就会去解决并发的冲突问题。

而这里面的优化问题，也不过是解决冲突问题的结果，当然还有 Core 和 Cache 彼此沟通的造成的成本问题，不过这不是核心点。

说这么多呢，就是想表达我写得好累……

重命名

重命名的意义在于解决乱序发射的 WAW（Write After Write，写后写），WAR（Write After Read，读后写）和RAW（Read After Write，写后读）问题。

乱序会产生这些问题的原因在于有限个数的寄存器，前后指令必然会使用重复的寄存器。

但是指令集不可能设立大量寄存器，而且这样也只是延缓问题，所以必须采用重命名技术，才能真正地乱序。

故而重命名被看作乱序 CPU 前后端的划分点。

相关性的冲突

这块较为复杂，应该使用例子去讲解，比如下面四条：

A: add r0,r1,r2
B: add r0,r3,r0
C: sub r5,r4,r6
D: sub r0,r8,49
____
A: add p30,p11,p12
B: add p31,p13,p30
C: sub p32,p14,p16
D: sub p33,p18,p19

其中 r 开头的寄存器是逻辑寄存器，p 开头的寄存器是物理寄存器。

• RAW：可以看见 A 和 B 的 r0 有 RAW 的关系，所以都应该重命名为 p30，保证一致性。
• WAW：可以看见 A 和 B 和 D 的 r0 有 WAW 的关系，对于 D 的 r0，它的旧有映射关系是来自 B 的 p31，而不是 RAT 读出结果，对于 B 来说，是 A 的 p30，需要检查 WAW，修改各条指令的旧有映射。
• WAR：可以看见 B 和 D 的 r0 有 WAR 的关系，重命名后无影响，不用考虑。

三种实现重命名的方法

由于需要存储寄存器的结果，我们可以想到两个组件：ARF（Arch Register File，逻辑寄存器堆）和 ROB（Reorder Buffer，重排序缓存）。

以此出现了三种设计思路，个人更欣赏第三个方法。

使用 ROB 实现重命名

任何指令在提交之前，它都是推测的，其数据会一直待在 ROB 中。提交后会写在 ARF 。

那么自然而然地可以想到使用 ROB 去扩展 ARF 的功能，我们只需要让 ROB 的编号作为物理寄存器编号与逻辑寄存器编号一一对应，便可以实现重命名的功能。

这也是英特尔部分 CPU 使用的方式。

优点：

• 容易实现，不复杂，可以简单地获得高性能。

缺点：

• 没有目的寄存器的指令不需要重命名，也会但是也会占用 ROB 的一个表项，浪费面积。
• 一个指令可以从 ROB 和 ARF 读取源操作数，要支持最坏的情况，即从 ROB 又从 ARF 读取数据，多端口对面积和时序有极大影响。

扩展 ARF 实现重命名

这种方法本质是 ROB 的延申，既然 ROB 用来做重命名有面积浪费，那么我们就把这个部分独立出来，这个被称为 PRF（Physical Register File，物理寄存器堆）。

也就是说，这个 FIFO 表项编号作为物理寄存器的编号。重命名时分配表项，指令退休后把结果写入 ARF，这个 FIFO 就可以释放相应表项。

优点：

• 相比使用 ROB 扩展，可以避免这部分面积浪费。

缺点：

• 依旧会有 ARF 和 PRF 的多端口问题。

统一的 PRF 实现重命名

我们可以把 ARF 和 PRF 合并，称为统一的 PRF（Physics Register File，物理寄存器堆），其中存储所有推测的和正确的寄存器值。

我们认为寄存器堆中所有没有和指令产生映射关系的都是空闲的指令。

为了标记这个情况，我们使用一个 freelist（空闲列表）来记录哪些寄存器处于空闲状态。通常使用 FIFO 来实现这个 Freelist。

优点：

• 寄存器只需要写一次，不需要反复移动数据，功耗上有优势
• 减少了原本多端口和多连线的问题

缺点：

• 较为复杂，需要更复杂的控制结构。

重命名过程的恢复

Checkpoints

等于做备份，每次分支预测或者中断做一次，结束后则放弃相应 checkpoint，恢复时直接复制回去。

优点是快，缺点是空间需求大。

WALK

ROB本身也存放这指令的历史状态，我们可以利用写端口不断地写回，更新回原本状态。

优点是不需要单独的空间存放备份，缺点是慢，分支预测失败的惩罚更大了。

Architecture state

这个拉完了，不采用不介绍。

RAT

无论什么重命名方式，都使用了重命名映射表（mapping table，常称为 RAT）。

它负责记录逻辑寄存器和物理寄存器编号的映射关系，源寄存器通过这个查找物理寄存器，目的寄存器要把相应物理寄存器写入表中。

它有两种物理实现方式：CAM 和 SRAM。

CAM

CAM 是对物理寄存器编号做编址，每个表项存放逻辑寄存器编号，在标记位有效且比较结果一致则匹配。

优点：checkpoint 成本低，每次只需要保存有效标志位，因为分配的可以直接丢弃。

缺点：访问速度和功耗比不过 SRAM。

SRAM

SRAM 是对逻辑寄存器编号做编址，每个表项存放物理寄存器编号，传入下标获取存放值来匹配。

提高分支预测正确率有助于减少 checkpoint 个数。

优点：由于 SRAM 访问快，面积小且功耗低，特别随着硬件规模变大，相对 CAM 优势很大。

缺点：恢复时要么使用大量面积做 checkpoint，要么消耗大量周期做 walk。

其余注意点

读写冲突

需要读优先，否则无法正确获取正确的过去映射关系

无目的寄存器的指令

对这种指令在解码过程就要标记：

1. 决定从 freelist 取出相应数量的寄存器
2. 目的寄存器读取 RAT，这些不用读
3. 使用源寄存器读取 RAT，比如说是立即数，也不读取
4. 忽视这些指令比较冲突

分发

这一步实际上就是把指令分发给 ROB 和 Issue 环节。

如果在 Issue 成为关键路径时，可以切级出来。

发射

分配电路

仲裁电路

唤醒电路

单周期

对于单周期指令，如果仲裁后可以直接去唤醒，因为也只是间隔一个周期，通过旁路电路就可以实现背靠背。

多周期

对于多周期指令有两种方式，延迟广播和延迟唤醒。

如果发现被仲裁电路选中的指令执行周期大于1，则在选中的当前周期，并不将这条指令的目的寄存器的编号送到总线上，而是根据这条被选中指令所需要执行的周期数（假设执行周期为N），延迟 N-1 个周期之后，才将它送到总线上。

这种方式会出现一个问题：假设乘法和加法共用一个 FU，他们由于间隔的问题，结果同时占用总线，这种情况下肯定是要增加唤醒总线的数量。可是这种多种操作公用 FU 的操作很常见，每个都加实在是太多了。

一个解决方法是：用一个表格记录当前 FU 执行指令所需要的操作数，后续仲裁的指令如果和这个表格发生冲突，那么不参与。

表格如果是和仲裁电路并行工作的，那么就可能出现周期的浪费，因为可能直接都被表格否定了；使用串行可以解决了这个问题，但是增加了时序。

在这种方法中,被仲裁电路选中的指令会按照正常的流程,在当前周期就将它的目的寄存器编号送到对应的总线上,并和 IQ 中所有的源寄存器进行比较。

但是,此时比较结果相等的寄存器并不一定马上被置为准备好的状态(也就是ready状态),而是根据这条进行广播的指令所需要的执行周期数,进行相应周期的延迟,然后再改变发射队列中源寄存器的状态,这就相当于延迟进行了唤醒。

这种方法不会影响唤醒过程的第一个阶段,被选中指令的目的寄存器的编号会按照正常的流程送到总线(tag bus)上,因此这种方法并不会增加对总线的需求,避免了上面方法中出现的问题。

这种方式需要需要寄存器资源少，并且总线需求不多

一周实现方式就是，在译码时我们就能知道这个执行需要多少周期，直接把这个周期填入 IQ，然后把周期数也同时传入总线即可

推测唤醒

因为 cache 命中率非常高，我们可以假设命中，如果 d-cache 采用物理地址，我们也假设 tlb 命中

假设周期是 issue -> rf -> cal addr -> tlb/tag -> data 的情况

如果 tlb 缺失，如果软件处理，由于异常，load需要放回去；并且硬件处理，load 指令没问题，只是 load 指令后续的指令需要放回发射队列。

D-cache 的不同组织方式，会影响这里的周期。

由于会replay，有两种方式，一种是把指令放在IQ保存，通过标记位去修改，这种会造成IQ的空间浪费，特别是miss的可能性实际上是比较少的。 另一种方式是专门搞一个RQ

读取

执行

负责执行的部件被称为 Function Unit(FU)，一般可区分的 FU 为 ALU（负责计算）、FPU（负责浮点计算）、BRU（负责控制程序流）、LSU（负责访问存储器）、特殊指令（看指令集）等等。

另一个重要部分就是旁路网络（bypassing network），负责把 FU 的运算结果送到需要它的地方，这是实现背靠背执行相邻指令的必要条件。

FU

由于 FU 的设计和指令集高度相关，这里只说明一些注意点和设计思路。

BRU

要考虑分支预测失败的情况，最简单的方式就是重命名是暂停流水线，等待 BRU 算完。

更好的方式是先用，算错了后，把后续指令全部 flush，对 RAT 恢复

LSU

访存也有冲突问题，但是我们不可能把它重命名化，因为地址是无限的或者说成本过高。

那么这里就可以出现三个方式，l和s都顺序，略

store指令顺序，两条store指令中的load指令乱序，就需要保存一个缓存，记录第一条指令store指令的地址和值，如果后续load的地址与其一致就直接获取值了。store只要选中，后续的load指令就可以参与仲裁。

这里还要判断store是不是在自己之前，因为第二条store可能先于部分load指令被选中，可以解码的时候给个编号，或者使用rob编号，rob编号过于稀疏

要考虑这里推测唤醒的问题

完全的乱序，这里store依旧是顺序，只是load不用考虑store了，也就是说store只比较最老的，load遵循oldest-first。

之所以这样考虑，是因为特别是RISC指令集，寄存器非常多，大部分变量存放在寄存器，访存中的RAW比较少见，这样可以获得更大的并行度。而CISC就不一样了

还需要讲一个非阻塞cache的操作方式，我们可以在cache miss时继续并行执行后面指令 要实现这个功能需要一个叫做MSHR（Miss Status/information Holding Register）的组件，会有首次缺失和再次缺失 首次缺失指的是对于一个给定的地址，访问D-Cache第一个产生的缺失成为首次 再次缺失指的是与首次缺失同一个cacheline 的load/store指令都会产生再次缺失，在还没有解决完首次缺失的情况下。 会有两个表，一个时mshr的本体，三项内容，valid表示首次缺失的占用，block address 指的是cahce line的数据块的公共地址，issued 是否开始处理发生首次缺失的指令 一个是 load/store table，无论发生的是首次还是再次，都会写入，valid，mshr entry（标记cache line），dest resgister，type，offset（数据块的位置） 这种对硬件开销太大，不好说。

关键字优先，让下一级存储器先从需要的读取，等于说cpu的执行和cache的填充同时工作

提前开始，也就是读出来需要的数据就可以让cpu继续执行了。

旁路

旁路有可能会过于长，因此很多情况会把这个阶段做成流水线的一个阶段，exe 前的阶段叫做 Source Drive，exe 后的阶段叫做 Reslut Drive

一个 FU 往往有多个计算单元，把不同的计算单元选出合适结果送到旁路网络，这个设计被称为 bypass sharing

bypass sharing 的冲突也是有的，比如一个 FU 中，有个指令要执行 3 个周期，结果一个周期后来了一条需要执行两个周期的指令，那么这个新指令就需要退回去。这里只需要设置一个控制寄存器，用相应位数代表第几个周期了。

几个可能要旁路电路的情况： FU 去唤醒 wakeup 电路 FU 的输出端到输入端 BRU 的输出端到 BPU

几个可能的阶段：

• 当两个相关指令处于相邻周期，这个旁路只能发生在exe和result drive。exe的输入和输出。
• 当两个相关指令之间差了一个周期，那就是 exe 和 writeback，或者source drive 和 result drive。writeback 和 read 没有
• source drive write back

并不一定要都用旁路，比如 LSU 地址计算需要用到 ALU，但是 ALU 不需要 LSU，所以可以有个单向的旁路即可

选择也是需要讲的，比如一个FU是否要来自PRF读，可以用一个bool来决定 每个指令可以看是否编号一样，因为是广播

Cluster

依旧可行，那就是直接把 FU 的旁路网络分开 TODO

提交

提交的way要和取值的way一样，免得堵塞。 ROB 本质是个 FIFO，因为 Rename 的顺序结构，保证了它的顺序结构。在 dispatch 写入 ROB。 没有异常，指令就可以离开ROB，有发生就继续处理

ROB的表项应该含有：

• Complete（是否执行完毕）
• Areg（逻辑目的寄存器)
• Rreg(物理目的寄存器)z
• Oreg（旧寄存器，用于恢复和aRAT）
• 异常类型
• pc值（用于发生中断方便执行程序）
• 指令类型（不同指令有不同结果，比如分支要释放checkpoint，store要些d-cache）

rob 每周期的退休指令不应该低于cpu设计的的way数，否则会爆

指令集定义的状态

可以使用 ROB 管理

可以使用物理寄存器管理 就是我们目前的写法

如果出现推测错误或者异常，那么这条指令后进入流水线的指令就不允许退休了，需要将这些指令抹掉，并且从ROB恢复状态。

另外要特殊关注store，因为它只有在退休的时候才可以真正修改处理器状态

精确异常

为了实现顺序的精确异常，异常应该在 commit 时处理